//===--- TypeWalker.cpp - Type Traversal ----------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
//  This file implements Type::walk.
//
//===----------------------------------------------------------------------===//

#include "polarphp/ast/TypeWalker.h"
#include "polarphp/ast/TypeVisitor.h"

namespace polar {

void TypeWalker::anchor() {}

namespace {

/// This class implements a simple type recursive traverser which queries a
/// user-provided walker class on every node in a type.
class Traversal : public TypeVisitor<Traversal, bool>
{
   using Base = TypeVisitor;
   friend Base;

   TypeWalker &Walker;

   bool visitErrorType(ErrorType *ty) { return false; }
   bool visitUnresolvedType(UnresolvedType *ty) { return false; }
   bool visitBuiltinType(BuiltinType *ty) { return false; }
   bool visitTypeAliasType(TypeAliasType *ty) {
      if (auto parent = ty->getParent())
         if (doIt(parent)) return true;

      for (auto arg : ty->getInnermostGenericArgs())
         if (doIt(arg))
            return true;

      return false;

   }
   bool visitPILTokenType(PILTokenType *ty) { return false; }

   bool visitParenType(ParenType *ty) {
      return doIt(ty->getUnderlyingType());
   }

   bool visitTupleType(TupleType *ty) {
      for (auto elementTy : ty->getElementTypes())
         if (doIt(elementTy))
            return true;
      return false;
   }

   bool visitReferenceStorageType(ReferenceStorageType *ty) {
      return doIt(ty->getReferentType());
   }

   bool visitNominalType(NominalType *ty) {
      if (auto parent = ty->getParent())
         return doIt(parent);
      return false;
   }

   bool visitAnyMetatypeType(AnyMetatypeType *ty) {
      return doIt(ty->getInstanceType());
   }

   bool visitModuleType(ModuleType *ty) { return false; }
   bool visitDynamicSelfType(DynamicSelfType *ty) {
      return doIt(ty->getSelfType());
   }
   bool visitSubstitutableType(SubstitutableType *ty) { return false; }

   bool visitDependentMemberType(DependentMemberType *ty) {
      return doIt(ty->getBase());
   }

   bool visitAnyFunctionType(AnyFunctionType *ty) {
      for (const auto &param : ty->getParams()) {
         if (doIt(param.getOldType()))
            return true;
      }

      return doIt(ty->getResult());
   }

   bool visitGenericFunctionType(GenericFunctionType *ty) {
      for (auto param : ty->getGenericParams())
         if (doIt(param))
            return true;

      for (const auto &req : ty->getRequirements()) {
         if (doIt(req.getFirstType()))
            return true;

         switch (req.getKind()) {
            case RequirementKind::SameType:
            case RequirementKind::Conformance:
            case RequirementKind::Superclass:
               if (doIt(req.getSecondType()))
                  return true;
               break;
            case RequirementKind::Layout:
               break;
         }
      }

      return visitAnyFunctionType(ty);
   }

   bool visitPILFunctionType(PILFunctionType *ty) {
      // TODO: Should this be the only kind of walk we allow?
      if (auto subs = ty->getSubstitutions()) {
         for (auto paramTy : subs.getReplacementTypes()) {
            if (doIt(paramTy))
               return true;
         }

         return false;
      }

      for (auto param : ty->getParameters())
         if (doIt(param.getInterfaceType()))
            return true;
      for (auto result : ty->getResults())
         if (doIt(result.getInterfaceType()))
            return true;
      if (ty->hasErrorResult())
         if (doIt(ty->getErrorResult().getInterfaceType()))
            return true;
      return false;
   }

   bool visitUnarySyntaxSugarType(UnarySyntaxSugarType *ty) {
      return doIt(ty->getBaseType());
   }

   bool visitDictionaryType(DictionaryType *ty) {
      return doIt(ty->getKeyType()) || doIt(ty->getValueType());
   }

   bool visitInterfaceCompositionType(InterfaceCompositionType *ty) {
      for (auto member : ty->getMembers())
         if (doIt(member))
            return true;
      return false;
   }

   bool visitLValueType(LValueType *ty) {
      return doIt(ty->getObjectType());
   }

   bool visitInOutType(InOutType *ty) {
      return doIt(ty->getObjectType());
   }

   bool visitUnboundGenericType(UnboundGenericType *ty) {
      if (auto parent = ty->getParent())
         return doIt(parent);
      return false;
   }

   bool visitBoundGenericType(BoundGenericType *ty) {
      if (auto parent = ty->getParent())
         if (doIt(parent))
            return true;

      for (auto arg : ty->getGenericArgs())
         if (doIt(arg))
            return true;

      return false;
   }

   bool visitArchetypeType(ArchetypeType *ty) {
      // If the root is an opaque archetype, visit its substitution replacement
      // types.
      if (auto opaqueRoot = dyn_cast<OpaqueTypeArchetypeType>(ty->getRoot())) {
         for (auto arg : opaqueRoot->getSubstitutions().getReplacementTypes()) {
            if (doIt(arg)) {
               return true;
            }
         }
      }
      return false;
   }

   bool visitTypeVariableType(TypeVariableType *ty) { return false; }

   bool visitPILBlockStorageType(PILBlockStorageType *ty) {
      return doIt(ty->getCaptureType());
   }

   bool visitPILBoxType(PILBoxType *ty) {
      for (Type type : ty->getSubstitutions().getReplacementTypes()) {
         if (type && doIt(type))
            return true;
      }
      return false;
   }

public:
   explicit Traversal(TypeWalker &walker) : Walker(walker) {}

   /// Returns true on failure.
   bool doIt(Type ty) {
      // Do the pre-order visitation.  If it returns false, we just
      // skip entering subnodes of this tree.
      switch (Walker.walkToTypePre(ty)) {
         case TypeWalker::Action::Continue:
            break;
         case TypeWalker::Action::SkipChildren:
            return false;
         case TypeWalker::Action::Stop:
            return true;
      }

      // Otherwise, visit the children.
      if (visit(ty))
         return true;

      // If we didn't bail out, do post-order visitation.
      switch (Walker.walkToTypePost(ty)) {
         case TypeWalker::Action::Continue:
            return false;
         case TypeWalker::Action::SkipChildren:
            llvm_unreachable("SkipChildren is not valid for a post-visit check");
         case TypeWalker::Action::Stop:
            return true;
      }
      llvm_unreachable("bad TypeWalker::Action");
   }
};

} // end anonymous namespace

bool Type::walk(TypeWalker &walker) const {
   return Traversal(walker).doIt(*this);
}

} // polar
